package binary

import "math"

func Sum(a, b int) int {
	if a == 0 {
		return b
	}
	cache := a
	a = (a & b ) << 1
	b ^= cache
	return Sum(a, b)
}

func Sum2(a, b int) int {
	var mid int
	for a != 0 {
		mid = a
		a = (a & b ) << 1
		b ^= mid
	}
	return b
}

func Reduce(a, b int) int {
	return Sum(a, Invert(b))
}

func Invert(num int) int {
	return Sum2(^num, 1)
}

func MultiplyProcess(a, b, ans int) int {
	// 当乘数为0时，则已经获取到了所有的累加和
	if b == 0 {
		return ans
	}
	// 如果b小于0，需要取反进行计算
	bLessZero := false
	if b < 0 {
		bLessZero = true
		b = Invert(b)
	}
	// 当前位置不等于0，累加结果
	if b & 1 != 0 {
		ans = Sum2(ans, a)
	}
	// 被乘数左移
	a <<= 1
	// 乘数右移
	b >>= 1
	// 恢复计算现场
	if bLessZero {
		b = Invert(b)
		ans = Invert(ans)
	}
	return MultiplyProcess(a, b, ans)
}

func Multiply2(a, b int) int {
	bLessZero := false
	if b < 0 {
		bLessZero = true
		b = Invert(b)
	}
	ans := 0
	for b != 0 {
		if b & 1 != 0 {
			ans += a
		}
		a <<= 1
		b >>= 1
	}
	if bLessZero {
		return Invert(ans)
	}
	return ans
}

func divide(dividend int, divisor int) int {
	if divisor == math.MinInt32 && dividend == math.MinInt32 {
		return 1
	} else if divisor == math.MinInt32{
		return 0
	} else if dividend == math.MinInt32 {
		if divisor == Invert(1) {
			return math.MaxInt32
		}
		ans := Div2(dividend, divisor)
		return Sum2(ans, Div2(Reduce(dividend, Multiply2(ans, divisor)), divisor))
	}
	return Div2(dividend, divisor)
}


func Div2(a, b int) int {
	isALessZero, isBLessZero := false, false
	if a < 0 {
		isALessZero = true
		a = Invert(a)
	}
	if b < 0 {
		isBLessZero = true
		b = Invert(b)
	}
	ans := 0
	for i:=62; i>=0; i-- {
		if (a >> i) >= b {
			ans |= 1<<i
			a = Reduce(a, b<<i)
		}
	}
	if isALessZero && isBLessZero {
		return ans
	} else if isALessZero || isBLessZero {
		return Invert(ans)
	}
	return ans
}